package com.ting.test.algorithms.查找算法.二分查找;

/**
 * 如何通过二分查找，找到数组内的任意一个波谷 局部最小值
 */
public class 二分查找扩展2 {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9, 10};
        int num = func(arr);
        System.out.println(num);
    }

    /**
     * 返回目标数据的下标
     * 没有则返回-1
     *
     * @param arr
     * @return
     */
    private static int func(int[] arr) {
        if (null == arr) {
            return -1;
        }
        if (arr.length == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            //如果0位置比1位置小 说明0位置就是一个局部最小值
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            //如果n-1位置比n-2位置小 说明n-2位置就是一个局部最小值
            return arr.length - 1;
        }


        //至此 可以知道 0位置和n-1位置都不是局部最小值
        //从0位置到1位置是一个向下的趋势
        //从n-1位置到n-2位置也是一个向下的位置 \
        //由此可以推出 在0位置到n-1位置之间一定有一个位置是局部最小值 \ ..?..  /

        int left = 0;
        int mid;
        int right = arr.length - 1;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                //如果mid比mid-1大 说明从mid-1 到mid是一个上升的趋势，
                // 而上文可知0~1是一个下降的趋势，因此在0~mid一定存在一个局部最小值
                right = mid;
            } else if (arr[mid] > arr[mid + 1]) {
                //如果mid比mid-1大 说明从mid-1 到mid是一个上升的趋势，
                // 而上文可知n-2到n-1是一个上升的趋势，因此在mid~n-1一定存在一个局部最小值
                left = mid;
            }else {
                //如果mid 的左边和右边都比他小 则说明mid是一个局部最小值 直接返回
                return mid;
            }

        }

        return -1;
    }
}
